package com.example.algorithm.tree.binaryTree;

import com.example.algorithm.linear.queue.Queue;

public class PagerFoldingTest {

    public static void main(String[] args) {
        //模拟折纸问题，打印每个结点
        Node<String> tree = createTree(3);
        printTree(tree);
    }

    //模拟对折n次
    public static Node<String> createTree(int N){

        //定义根节点
        Node<String> root = null;
        for (int i = 0; i < N; i++) {
            //当前是第一次对折
            if (i == 0){
                root = new Node<String>("down",null,null);
                continue;
            }
            //不是第一次对折
            //定义一个辅助队列，层序遍历思想，给叶子结点添加子结点
            Queue<Node> queue = new Queue<>();
            queue.enqueue(root);
            //遍历
            while (!queue.isEmpty()){
                //从队列中弹出结点
                Node tmp = queue.dequeue();
                //如果左子结点，把左子节点放入队列中
                if (tmp.left != null){
                    queue.enqueue(tmp.left);
                }
                //如果柚子节点，把右子节点放入队列中
                if (tmp.right != null){
                    queue.enqueue(tmp.right);
                }
                //如果没左和右子结点，是叶子结点，需要给结点添加左子节点和右子节点
                if (tmp.left == null && tmp.right == null){
                    tmp.left = new Node ("down",null,null);
                    tmp.right = new Node("up",null,null);
                }
            }
        }


        return root;
    }

    //打印
    public static void printTree(Node root){
        if (root == null){
            return;
        }

        if (root.left!=null){
            printTree(root.left);
        }

        System.out.println(root.item);

        if (root.right!=null){
            printTree(root.right);
        }
    }

    public static class Node<T>{
        public T item;

        public Node left;

        public Node right;

        public Node(T item, Node left, Node right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }
    }

}
